/**
 * https://leetcode-cn.com/problems/word-search/
 * 单词搜索
 * 给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。
 * 单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
 * @param board
 * @param word
 */
const exist = (board: string[][], word: string): boolean => {
  let ans = false;

  // 网状格中行的数量
  const rowL = board.length;


  // 网状格中列的数量
  const colL = board[0].length;
  const wL = word.length;

  const dfs = (
    row: number,
    col: number,
    curIndex: number,
    mark: boolean[][]
  ): boolean => {
    // 单词已经找到了
    if (curIndex === wL) return true;

    let res = false;

    // 往四方查找
    // 往上找
    if (
      row > 0 &&
      !mark[row - 1][col] &&
      !res &&
      board[row - 1][col] === word[curIndex]
    ) {
      mark[row - 1][col] = true;
      res = dfs(row - 1, col, curIndex + 1, mark);
    }

    // 往右找
    if (
      col < colL - 1 &&
      !mark[row][col + 1] &&
      !res &&
      board[row][col + 1] === word[curIndex]
    ) {
      mark[row][col + 1] = true;
      res = dfs(row, col + 1, curIndex + 1, mark);
    }

    // 往下找
    if (
      row < rowL - 1 &&
      !mark[row + 1][col] &&
      !res &&
      board[row + 1][col] === word[curIndex]
    ) {
      mark[row + 1][col] = true;
      res = dfs(row + 1, col, curIndex + 1, mark);
    }

    // 往左找
    if (
      col > 0 &&
      !mark[row][col - 1] &&
      !res &&
      board[row][col - 1] === word[curIndex]
    ) {
      mark[row][col - 1] = true;
      res = dfs(row, col - 1, curIndex + 1, mark);
    }

    // 当前标记为false, 未找到
    if (!res) {
      mark[row][col] = false;
    }

    return res;
  };

  for (let i = 0; i < rowL; i++) {
    for (let j = 0; j < colL; j++) {
      if (board[i][j] === word[0]) {
        // 找到的首个字母, 创建二维数组标记找到的位置
        // 默认都没有找到
        const mark: boolean[][] = new Array(rowL)
          .fill(0)
          .map((_) => new Array(colL).fill(false));

        // 标记当前已经找找过了
        mark[i][j] = true;
        const ret = dfs(i, j, 1, mark);
        if (ret) return true;
      }
    }
  }

  return ans;
};

console.log(
  exist(
    [
      ["A", "B", "C", "E"],
      ["S", "F", "C", "S"],
      ["A", "D", "E", "E"],
    ],
    "CCE"
  )
);
